A large amount of prior art exists in the area of font design and text layout for digital typography. Computer aided font design tools have been created since the 1960's. Fonts were typically rendered in media such as metal slugs or photomasks for phototypesetters. Now, fonts are frequently rendered in digital form for use in digital computers and digital display devices, in order to produce output in a particular typeface design.
A font is typically defined as a set of printable or displayable text characters of specific style and size. A design of a set of fonts is called a typeface. A wide range of character shapes exist for representing given alphanumeric characters or typographic symbols such as numbers, letters, punctuation marks and dingbats. Each such shape is distinguished by its various design features such as underlying geometry, stroke thickness, character height, serifs, joinery, placement and number of contours and ratio of thin-to-thick strokes. Existing digital font-rendering techniques can be classified into bit map type and outline type.
In the bit map rendering technique, the glyphs of the fonts are described and manipulated as explicit bit maps. A bit map representation must be provided for each font point size, as automatic sizing generally cannot be performed for a bit mapped font. Bit map rendering techniques are a direct way to display fonts. Bit mapping representations, however, consume a sizable amount of computer memory for storing the various different varieties of typefaces and the many different point sizes for each typeface. Thus, while bit map rendering techniques are often still used, other techniques are typically preferred in many circumstances, particularly when it is desirable to minimize the usage of computer memory.
An outline font is a font in which the outlines of each character are geometrically defined. Each character of such fonts is described by vector geometry and can be scaled with ease. The curves between the endpoints of the vectors are usually specified by using either cubic or linear Bezier spline curves. Spline curves are smooth piecewise polynomials that can be used to represent functions over large intervals. While the most obvious relevance of text characters is for printing and publications, other applications such as computer animation and computer aided design require text manipulation functions. Spline curves are controlled by a small set of given control points, which are often located on the outline or otherwise associated with the outline as in the case of tangent points. Popular outline fonts in use today are the True Type used by Microsoft Windows, and the Adobe's Type 1 fonts, as described in The True Type font format specification, Microsoft Corporation, 1990, and in Adobe type 1 font format: multiple master extensions, Adobe Developer Support, 1992, the contents of which are hereby incorporated by reference. Representing symbol images by outlines not only obviates large memory storage but also permits interactive font editing and text placement.
Many computerized systems employ printing methods that layout text strings along smooth lines and curves. Such algorithms are found in systems that employ outline fonts: for example the PostScript language and the Microsoft Office “WordArt” package.
In V. Ostromoukhov and R. D. Hersch, “Artistic screening”, SIGGRAPH '95, (1995), pp. 219-228, the authors describe a two dimensional morphing method in which each elementary sub-screen shape is defined by a letter shape toward half-toning. This technique is applied in artistic screening, which incorporates both full size and microscopic letters into the image reproduction process.
Existing text deformation techniques perform the deformations in one of two ways. The first approach defines a best-suited rigid motion transformation for each symbol, as described in pages 171-173, of the “Program 11/Placing Text Along an Arbitrary Path” in the PostScript Language Tutorial and Cookbook. This approach is also one of the methods used by the “WordArt” package.
The second common technique maps the control points of the Bezier curves comprising the text symbol. Reed in U.S. Pat. No. 5,715,473 describes a method and apparatus for providing a set of variations of control points of a symbol image, such as a glyph, for display of at least one variation of the symbol image on a display device of a computer controlled display system. The method includes providing a set of control points specifying the outlines of the symbol image and providing variation data for specifying a set of variations for at least one of the control points. The variation data specifies a spatial manipulation of the font control, thereby modifying the outline of the symbol image.
Brock in U.S. Pat. No. 5,949,435 describes a computer-implemented apparatus and method for generating an output digital font from a base font and one or more font descriptor files. The method involves retrieving a file containing instructions and data for a generic base font, retrieving a font descriptor file containing specifications for operating upon the base font to produce the desired output font, and then generating the output font by performing operations upon the base font in accordance with the specifications contained in the font descriptor file. Brock's method produces a character program for each character in the base font.
The control point mapping method is better than rigid motion transformation, since it is more accurate. When there are enough control points to approximate the curve well by its control polygon, the deformed letters will look better. Nevertheless, neither method guarantees that the letters after the deformation will be intersection free. For the second method such intersection artifacts do not occur frequently after control point mapping, but still exist. Reference is now made to FIG. 1, which demonstrates the creation of an intersection due to control point mapping. FIG. 1a comprises straight-line segments 10 and 12, placed relative to base line 14. In FIG. 1a the undeformed linear edges of a character do not intersect each other. FIG. 1b shows the deformed base line 24, with mapped end control points and edges. The straight-line edges, 20 and 22, intersect each other, and the shape expands below the base line 24. The lengths of the dashed lines normal to the base line are unmodified.
Another problem with the control point mapping approach is that all linear segments of the symbol stay linear, with possible displeasing artifacts that affect the continuity of adjacent segments. Reference is now made to FIG. 2, which shows a simple example of this behavior. FIG. 2a comprises a letter ‘A’ 30, placed along a linear base line 32. The letter ‘A’ has several linear segments. In FIG. 2b, only the control points of the Bezier curves comprising the symbol ‘A’ are mapped. The linear segments forming the letter ‘A’ 40 remain linear, and do not follow the shape of the deformed base line 42.
In T. W. Sedergerg and S. R. Parry, “Free-form deformation of solid geometric models”, SIGGRAPH '86, 20(4): 151-160, 1986, a freeform deformation technique is presented for solid geometric models. Given a mapping M from R3 to R3 and an object O from R3, where R3 denotes a three-dimensional space, O can be warped to follow M as M(O). M provides a precise control over the warping process. The volume deformation technique is not directly applicable to font and text design and manipulation, as these require a two-dimensional deformation.
Contents of the above books and articles are hereby incorporated by reference.
There is a need for a deformation technique for manipulation and placement of shapes over a two-dimensional or three-dimensional freeform surface, which provides precise control over all shape segments, and avoids intersections. There is a further need for a technique enabling precise placement of shapes along a specified base line, so that the shapes smoothly follow the base line.